package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

/**
 * 求完全二叉树的节点个数<br/>
 * 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
 *
 * @author zhanghp
 * @since 2024/4/19 11:33
 */
public class Code09_CountCompleteTreeNodes {
    static class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return f(root, 1, mostLeft(root, 1));
        }

        // cur : 当前来到的节点
        // level :  当前来到的节点在第几层
        // deepth : 整棵树的高度，不是cur这棵子树的高度
        // 求 : cur这棵子树上有多少节点
        public int f(TreeNode cur, int level, int deepth) {
            if (level == deepth) {
                return 1;
            }
            // 右侧最左节点深度和树的整体深度，相等，则左树是完全满二叉树
            if (mostLeft(cur.right, level + 1) == deepth) {
                // 左树的所有节点 2^n - 1
                // 在加根节点，2^n
                // 左树和根  +  右树节点
                return (1 << (deepth - level)) + f(cur.right, level + 1, deepth);
            } else {
                return 1;
            }
        }

        public int mostLeft(TreeNode head, int level) {
            while (head != null) {
                level++;
                head = head.left;
            }
            // while判断，首先判断的是head，所以把判断head减掉一次
            return level - 1;
        }
    }
}
